package main.剑指OfferⅡ;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Day33_Day36 {
    public static void main(String[] args) {
        System.out.println("**************************Day33**************************");
        System.out.println("剑指OfferⅡ097.子序列的数目");
        System.out.println("剑指OfferⅡ098.路径的数目");
        System.out.println("剑指OfferⅡ099.最小路径之和");
        System.out.println("**************************Day34**************************");
        System.out.println("剑指OfferⅡ100. 三角形中最小路径之和");
        System.out.println("剑指OfferⅡ101.分割等和子集");
        System.out.println("剑指OfferⅡ102.加减的目标值");
        System.out.println("**************************Day35**************************");
        System.out.println("剑指OfferⅡ103.最少的硬币数目");
        System.out.println("剑指OfferⅡ104.排列的数目");
        System.out.println("**************************Day36**************************");
        System.out.println("剑指OfferⅡ105.岛屿的最大面积");
        System.out.println("剑指OfferⅡ106.二分图");
        System.out.println("剑指OfferⅡ107.矩阵中的距离");
    }
}

class Offer97{
    public int numDistinct(String s, String t) {
        int length1=s.length(),length2=t.length();
        if (length1<length2) return 0;
        char[] str1=s.toCharArray(),str2=t.toCharArray();
        int[][] dp=new int[length1+1][length2+1];
        for (int i=0;i<=length1;i++) dp[i][length2]=1;
        for (int i=length1-1;i>=0;i--){
            for (int j=length2-1;j>=0;j--){
                if (str1[i]==str2[j]) dp[i][j]=dp[i+1][j+1]+dp[i+1][j];
                else dp[i][j]=dp[i+1][j];
            }
        }
        return dp[0][0];
    }
}

class Offer98{
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (i==0||j==0) dp[i][j]=1;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

class Offer99{
    public int minPathSum(int[][] grid) {
        int row= grid.length,col=grid[0].length;
        int[][] dp=new int[row][col];
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (i==0&&j==0) dp[i][j]=grid[i][j];
                else if (i==0) dp[i][j]=dp[i][j-1]+grid[i][j];
                else if (j==0) dp[i][j]=dp[i-1][j]+grid[i][j];
                else dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[row-1][col-1];
    }
}

class Offer100{
    public int minimumTotal(List<List<Integer>> triangle) {
        int row= triangle.size(),col=triangle.get(row-1).size(),min=Integer.MAX_VALUE;
        int[][] dp=new int[row][col];
        dp[0][0]=triangle.get(0).get(0);
        for (int i=1;i<row;i++){
            List<Integer> curList=triangle.get(i);
            for (int j=0;j<=i;j++){
                if (j==0) dp[i][j]=dp[i-1][j]+curList.get(0);
                else if (i==j) dp[i][j]=dp[i-1][j-1]+curList.get(j);
                else {
                    dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1])+curList.get(j);
                }
            }
        }
        for (int num:dp[row-1]){
            min=Math.min(min,num);
        }
        return min;
    }
}

class Offer101{
    public boolean canPartition(int[] nums) {
        int m=0;
        for (int num:nums) m+=num;
        if (m%2!=0) return false;
        m/=2;
        boolean[] dp=new boolean[m+1];
        dp[0]=true;
        for (int x:nums){
            for (int j=m;j>=x;j--){
                dp[j]|=dp[j-x];
            }
        }
        return dp[m];
    }
}

class Offer102{
    int[] arr;
    int target,count;
    public void process(int index,int curSum){
        if (index==arr.length&&curSum==target) {
            count++;
            return;
        }else if (index==arr.length&&curSum!=target) return;
        process(index+1,curSum+arr[index]);//+
        process(index+1,curSum-arr[index]);//-
    }
    public int findTargetSumWays(int[] nums, int target) {
        this.arr=nums;
        this.target=target;
        count=0;
        process(0,0);
        return count;
    }
}

class Offer103{
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Offer104{
    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for (int i=1;i< dp.length;i++){
            int count=0;
            for (int j=0;j< nums.length;j++){
                count+= i-nums[j]>=0? dp[i-nums[j]] : 0;
            }
            dp[i]=count;
        }
        return dp[target];
    }
}

class Offer105{
    int count;
    public void process(int row,int col,int[][] grid){
        count++;
        grid[row][col]=0;
        if (row-1>=0&&grid[row-1][col]==1) process(row-1,col,grid);//上
        if (row+1< grid.length&&grid[row+1][col]==1) process(row+1,col,grid);//下
        if (col-1>=0&&grid[row][col-1]==1) process(row,col-1,grid);//左
        if (col+1<grid[0].length&&grid[row][col+1]==1) process(row,col+1,grid);//右
    }
    public int maxAreaOfIsland(int[][] grid) {
        int max=0;
        for (int i=0;i< grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]==1){
                    count=0;
                    process(i,j,grid.clone());
                    max=Math.max(max,count);
                }
            }
        }
        return max;
    }
}

class Offer106{
    private static final int UNCOLORED = 0;
    private static final int RED = 1;
    private static final int GREEN = 2;
    private int[] color;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        color = new int[n];
        Arrays.fill(color, UNCOLORED);
        for (int i = 0; i < n; ++i) {
            if (color[i] == UNCOLORED) {
                Queue<Integer> queue = new LinkedList<Integer>();
                queue.offer(i);
                color[i] = RED;
                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    int cNei = color[node] == RED ? GREEN : RED;
                    for (int neighbor : graph[node]) {
                        if (color[neighbor] == UNCOLORED) {
                            queue.offer(neighbor);
                            color[neighbor] = cNei;
                        } else if (color[neighbor] != cNei) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

class Offer107{
    public int[][] updateMatrix(int[][] mat) {
        int row = mat.length,col = mat[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();// 用于存入处理的点
        for (int i = 0; i < row; i++) {// 先找到0的点位
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 0) {
                    queue.add(new int[]{i, j});
                } else {
                    mat[i][j] = -1;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            if (i != 0 && mat[i-1][j] == -1) {// 上面
                mat[i-1][j] = mat[i][j] + 1;
                queue.add(new int[]{i-1, j});
            }
            if (j!=0 && mat[i][j-1] == -1) {// 左侧
                mat[i][j-1] = mat[i][j] + 1;
                queue.add(new int[]{i, j-1});
            }
            if (j != col-1 && mat[i][j+1] == -1) {// 右侧
                mat[i][j+1] = mat[i][j] + 1;
                queue.add(new int[]{i, j+1});
            }
            if (i != row-1 && mat[i+1][j] == -1) {// 下侧
                mat[i+1][j] = mat[i][j] + 1;
                queue.add(new int[]{i+1, j});
            }
        }
        return mat;
    }
}